
import java.util.Iterator;
import java.util.LinkedList;

public class GraphConversion {
       
        private static  int m_maxHeight = 0;
       
        public static int HeightInitialization(SimpleGraph G)
        {
        	 Vertex source = new Vertex(null,null);
             Iterator vertices =  G.vertices();
             while(vertices.hasNext())
             {
                     source = (Vertex)vertices.next();
                     if(source.getName().equals("s"))
                             break;
             }

             if(!source.getName().equals("s"))
                     return 0;
             return BFS(source);

        }

        public static int BFS(Vertex v)
        {
               
        	 if(v.getName().equals("t"))
             {
                     ((VertexData)v.getData()).setHeight(0);
                     return 0;
             }
             ((VertexData)v.getData()).setVisited();
             //change
             int num = m_maxHeight;
            
             LinkedList childVertex = new LinkedList();
             Iterator incidentEdges = v.incidentEdgeList.iterator();
             while(incidentEdges.hasNext())
             {
                     Edge e = (Edge) incidentEdges.next();
                     if(e.getFirstEndpoint().equals(v))
                     {
                             Vertex w = e.getSecondEndpoint();
                             childVertex.add(w);
                     }
             }                      
             Iterator child = childVertex.iterator();
            
             while(child.hasNext())
             {
                     Vertex c = (Vertex) child.next();
                     int i = num;
                     if(!((VertexData)c.getData()).isVisited())
                             i = BFS(c);
                     else
                             i = ((VertexData)c.getData()).getHeight();
                     if(i < num)
                             num = i;
             }
             num += 1;
             if(!(v.getName().equals("s")))
                     ((VertexData)v.getData()).setHeight(num);
             return num;    
        }
       
        /**
         * @param The simple graph we'd run in our algorithm
         * Initial the EdgeData, and put them to data variable
         */
        public static void ConvertGraph(SimpleGraph G)
        {
        	m_maxHeight = G.numVertices();
            Iterator edges =  G.edges();
            //initial every edges;
            while(edges.hasNext())
            {
                    Edge edge = (Edge)edges.next();
                    Double capacity = (Double) edge.getData();
                    EdgeData data = new EdgeData(capacity);
                    edge.setData(data);
            }
            //initial every vertex
            Iterator vertices =  G.vertices();
            while(vertices.hasNext())
            {
                    Vertex vertex = (Vertex)vertices.next();
                    VertexData vertexData = new VertexData();
                    if(vertex.getName().equals("s"))
                    {
                            vertexData.setHeight(G.numVertices());
                    }
                    vertexData.setVisited(false);
                    vertex.setData(vertexData);
            }
           
            return;

        }
       
             
   	public void test(String filename) throws NumberFormatException, Exception {
		// TODO Auto-generated method stub
		SimpleGraph G = new SimpleGraph();
		SimpleGraph G1 = new SimpleGraph();
		SimpleGraph G2 = new SimpleGraph();
		SimpleGraph G3 = new SimpleGraph();
		SimpleGraph G4 = new SimpleGraph();
		SimpleGraph G5 = new SimpleGraph();
		int flow_max,max_flow_pp,max_flow2_pp_eh,flow_FF,preflow_FIFO;		
		//	GraphInput.LoadSimpleGraph(G, "/home/iyer/Algorithms/Project/25-20-1-5-30.txt");
		SimpleGraph[] Graphs = {G,G2,G3,G4,G5};
		
			for(int i =0; i!=Graphs.length;++i)
			{
				GraphInput.LoadSimpleGraph(Graphs[i], "/Users/Tina/Documents/workspace/TCSS543_Project/" + filename);
			}
		System.out.print("no. nodes: " + G.numVertices() +" no. edges: "+G.numEdges() +"\n");
		
		ConvertGraph(G);
		PreflowPush preflow ;
		EnhancedPreflow enh_Preflow ;
		int i = HeightInitialization(G);
		StopWatch time_PP = new StopWatch();
        
        try
        {           
            preflow = new PreflowPush(G);
            //basic Preflow
            max_flow_pp = preflow.MaxFlow(false);
//            System.out.println( + max_flow_pp);
            System.out.println("Preflow max flow: " + max_flow_pp);
            System.out.println(time_PP.elapsedTime());
//        	System.out.println("Elapsed Time for the whole max flow Preflow: "+time_PP.elapsedTime());
        }
        catch(Exception e1)
        {
        	
        }
        
		ConvertGraph(G2);
		StopWatch time = new StopWatch();
		//System.out.println("Elapsed Time for the loading graph : "+time.elapsedTime());
		try {
            
            flow_max = ScalingMaxFlow.maxFlow(G2, (Vertex)G2.vertexList.getFirst(), (Vertex)G2.vertexList.getLast());
            //System.out.println("source and sink vertices" +(((Vertex) G.vertexList.getFirst()).getName()) + ((Vertex) G.vertexList.getLast()).getName());
            System.out.println("Scaling max flow: " + flow_max);
            System.out.println(ScalingMaxFlow.dfs_time.elapsedTime());
    
			} 
		catch (Exception e1)
		{
            e1.printStackTrace();
        }
		
		ConvertGraph(G3);
		StopWatch time_FF = new StopWatch();
	
       
        try
        {
        	flow_FF =  FordFulkerson.maxFlow(G3,(Vertex)G3.vertexList.getFirst(), (Vertex)G3.vertexList.getLast());
        	System.out.println("FF max flow: " + flow_FF);
        	//System.out.println( flow_FF);
        	//System.out.println(FordFulkerson.dfs_time_FF.elapsedTime());
        	System.out.println( time_FF.elapsedTime());
        	
           // System.out.println("time for dfs alone FF :" + FordFulkerson.dfs_time_FF.elapsedTime() );
        	//System.out.println("Elapsed Time for the whole max flow : "+time_FF.elapsedTime());
        	
        }
        catch(Exception e1)
        {
        	e1.printStackTrace();
        }
          	
    		ConvertGraph(G4);
    		HeightInitialization(G4);
            StopWatch time_PP_enh = new StopWatch();
            try
            {
            	enh_Preflow = new EnhancedPreflow(G4);
            	max_flow2_pp_eh= enh_Preflow.MaxFlow();
            	System.out.println("Preflow enhanced max flow: " + max_flow2_pp_eh);
            	System.out.println(+time_PP_enh.elapsedTime());
            	  
              	//System.out.println("Elapsed Time for the whole max flow Preflow enhanced: "+time_PP_enh.elapsedTime());
            	  
            }
            catch(Exception e1)
            {
            	
            }

          ConvertGraph(G5);
    		HeightInitialization(G5);
            StopWatch time_PP_FIFO = new StopWatch();
            try
            {
            	PreflowPush Preflow_FIIO = new PreflowPush(G5);
            	preflow_FIFO= Preflow_FIIO.MaxFlow(true);
            	System.out.println("Preflow FIFO max flow: " + preflow_FIFO);
            	System.out.println(+time_PP_FIFO.elapsedTime());
            	  
            	//  System.out.println("Preflow enhanced max flow: " + max_flow2_pp_eh);
              	//System.out.println("Elapsed Time for the whole max flow Preflow enhanced: "+time_PP_enh.elapsedTime());
            	  
            }
            catch(Exception e1)
            {
            	
            }
		}
    		
}


